package cn.edu.xjtu.work.inorderTraversal;

import java.util.ArrayList;
import java.util.List;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 94. 二叉树的中序遍历
 * 
 * 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
 */
public class Solution {
  public static void main(String[] args) {
    System.out.println(inorderTraversal(null));
  }

  /**
   * 递归中序遍历,深度优先
   * 
   * @param root
   * @return
   */
  public static List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ret = new ArrayList<>();
    traversal(root, ret);
    return ret;
  }

  public static void traversal(TreeNode node, List<Integer> ret) {
    if (node == null) {
      return;
    }
    traversal(node.left, ret);
    ret.add(node.val);
    traversal(node.right, ret);
  }
}
